The present invention relates to a method of scheduling resources and in particular scheduling access to resources for the efficient utilisation of network capacity and network infrastructure.
The deployment of dedicated high performance networked infrastructure for high-end applications and services such as e-health, e-commerce, digital cinema, scientific visualization, and big data analysis requires mechanisms which ensure effective and efficient use of available resources such as processing power, data storage, and network capacity. Key to achieving this is the development and deployment of intelligent request scheduling and service provisioning within the network infrastructure.
FIG. 1 shows a schematic depiction of an architecture of a such a high-performance communications network 100. The communications network 100 comprises: network controller 110, data centre 120, a plurality of network nodes 130a, 130b, . . . , 130f and first and second network users 140a, 140b. The plurality of network nodes 130a, 130b, . . . , 130f are interconnected by a plurality of communications links 150 and the data centre 120 and the first and second network users 140a, 140b are each connected to one of the plurality of network nodes by a respective communication link 150. The plurality of communications links 150 can be configured dynamically to provide high quality of service (QoS) networked services for scheduled requests. The network controller 110 receives requests for scheduling from users and will grant or refuse these requests in accordance with the availability of the requested network resources. The network controller also comprises an integrated control plane for service provisioning across the plurality of network nodes and communications links.
Such architectures are becoming popular with the emergence of technological approaches such as Software Defined Networking (SDN) which promote the existence of logically centralized network control functionalities which dynamically program the forwarding plane of network devices (see, for example, “Software-Defined Networking: The New Norm for Networks”, Open Networking Foundation, ONF White Paper, 2012). Such scenarios focus on high-end applications which require network capacities that preclude traditional public networks and instead require the use of dedicated networked infrastructures. For example, the networked distribution of ultra-high-definition video and big data datasets (e.g. financial market datasets) have bandwidth requirements ranging from hundreds of megabits per second (Mb/s) up to terabits per second (Tb/s) for a single request (see A. Jukan & J. Mambretti, “Evolution of Optical Networking Toward Rich Digital Media Services”, Proceedings of IEEE, Vol. 100 Issue 4, 2012).
Table 1 below shows a number of requests which may be made of the network discussed above with reference to FIG. 1 from digital cinema clients and bank data archiving applications. The network infrastructure controller takes into consideration resource requirements such as bandwidth, which is a capacity constraint, as well as service delivery times when scheduling requests. For digital cinema clients i.e. cinema theatres, requests are usually known in advance and a schedule can be computed statically. Bank data archiving could also be performed routinely at predetermined times and thus can also be scheduled statically.
TABLE 1Requests for networked servicesClientBandwidth RequirementTimeslotDigital Cinema - Movie A250 Mb/sT1Digital Cinema - Movie B250 Mb/sT1Digital Cinema - Movie C400 Mb/sT2Bank - Routine Archiving100 Mb/sT1-T2
FIG. 2 shows a graphical depiction of a schedule timeline, which can be derived from the scheduling of requests shown in Table 1 above. This assumes the scheduling algorithm aims to achieve multiple objectives including:                (i) maximizing the number of accepted requests with sufficient end-to-end bandwidth, and        (ii) minimizing the number of network links used to interconnect the service provider's data centre with clients for accepted requests.        
However, it will be understood that all not all uses of the network can be scheduled in such a predetermined or static manner. Consider the case where a critical threat to the banking system requires the immediate real time remote storage of large datasets with the requirement presented in Table 2 below.
TABLE 2Further request for networked servicesClientBandwidth RequirementTimeslotBank - Critical Archiving750 Mb/sT2
FIG. 3 shows a graphical depiction of the schedule timeline of FIG. 2 which has been modified to incorporate the further request shown above in Table 1. This schedule will cause the network to have insufficient capacity to transport this dataset across the networked infrastructure with high enough QoS for remote storage at networked storage facility 160. Therefore a reactive scheduler is required to reshuffle the scheduled tasks which fall within the same timeslot as the real time critical bank data archiving request.
A schedule is the ordering of requests into time sequences with a corresponding selection of resources required to execute or implement the requests. The execution of a schedule results in the delivery of services to clients systems over a specified time horizon. Scheduling problems can be divided into two categories: static scheduling, where requests are submitted in advance, and dynamic scheduling, in which requests arrive in real time. Static scheduling is typically preformed in environments where time constraints are not critical and a full optimisation can be performed to deliver an optimal schedule. Such scenarios mainly apply to start of the day scheduling which takes into account the requests from previous days that are already in the pipeline. The execution time for a static scheduler can range from a few minutes to few hours while taking into consideration a wide range of constraints and optimisation goals. However, such approaches are not valid in an environment where time is critical and a schedule has to be prepared as and when requests arrive in real time. A real time scheduler allows decisions to be made quickly and optimally, allowing time critical decisions to happen with very little manual intervention.
US2009/0089092 discloses a method of scheduling resources used in delivering healthcare services to a series of patients. The method identifies the availability of a series of resources used to deliver the healthcare; calculates a schedule including a block of time dependent on the predicted duration for each resource to deliver healthcare; calculates a confidence level in the schedule, the confidence level including a probability that one or more of the resources will not be available; and outputs the schedule and the confidence level in the schedule for display.
According to a first aspect of the present there is provided a method of scheduling a plurality of tasks to one or more of a plurality of resources such that the tasks can be executed, the method comprising the steps of: a) in a first phase of the method, assigning one or more tasks when the task is received to one or more of the plurality of resources for execution at a pre-determined time; b) in a second phase of the method, i) monitoring each of the plurality of resources to determine the likelihood that each of the tasks can be executed; ii) if the likelihood that a task cannot be executed is greater than a predetermined threshold, reassigning the task to one or more further resources such that there is a sufficient likelihood that the task can be executed at the pre-determined time by the one or more further resources; and c) in a third phase of the method, optimising the scheduling of one or more of the tasks, characterised in that the third phase comprises: for each task calculating a score using a first fuzzy logic function and deciding whether to select a task for optimisation in accordance with the calculated score, for the one or more tasks selected for optimisation using a second fuzzy logic function to optimise the allocation of the selected tasks to the plurality of resources.
The optimisation of the allocation of the selected tasks to the plurality of resources may comprise the allocation of a selected task from a first resource to a second resource. Alternatively, the optimisation of the allocation of the selected tasks to the plurality of resources may comprise the allocation of a selected task from a first timeslot to a second timeslot. This may involve swapping a first selected task with a second selected task, the first and second tasks being scheduled to be executed in different timeslots.
The present invention provides a scheduling method without a strict separation between predictive and reactive scheduling processes. It exposes configurable drivers sent to the engine to facilitate dynamic handling of task and/or resource assignments depending on current time.
According to a second aspect of the present invention there is provided a data carrier device comprising computer executable code for performing a method as described above.
According to a third aspect of the present invention there is provided an apparatus configured to, in use, perform a method as described above.